#include <stdio.h>
#include <stdlib.h>
#include<stdbool.h>

//定义二叉树结构
typedef struct Treenode
{
    int val;
    Treenode* left;
    Treenode* right;
} Treenode;

typedef struct QNode
{
    Treenode* Node;
    QNode* next;
} QNode;

typedef struct Queue
{
    QNode* front;
    QNode* rear;
} Queue;

void QueueInit(Queue* q)
{
    q->front = q->rear = (Queue*)malloc(sizeof(QNode));
    q->front->next = NULL;
}

Treenode* DeQueue(Queue* q)
{
    if (q->front == NULL) 
        return NULL;
    
    Treenode* out = q->front->Node;

    if (q->front->next == NULL)
    {
        q->front = q->rear = NULL;
    }
    free(q->front);
    return out;
}

void Enqueue(Queue* q,QNode* root)
{

}

int IsEmpty(Queue* q)
{
    return q->front == q->rear;
}

void LevelOrder(Treenode* root)
{
    if (!root)
    {
        return;
    }

    Queue* q;
    QueueInit(q);
    Enqueue(q,root);

    while(!IsEmpty(q))
    {
        Treenode* node = DeQueue(q);
        printf("%d", node->val);

        if (root->left)
        {
            Enqueue(q, root->left);
        }

        if (root->right)
        {
            Enqueue(q,root->right);
        }
    }

    while (!IsEmpty(q))
    {
        DeQueue(q);
    }
    free(q->front);
}

